package leet93restoreipaddress

// https://leetcode.cn/problems/restore-ip-addresses/

func restoreIpAddresses(s string) []string {
	var res []string
	var path []string

	var backtrack func(start int)
	backtrack = func(start int) {
		if len(path) == 4 && start == len(s) {
			res = append(res, join(path, "."))
			return
		}
		if len(path) >= 4 || start >= len(s) {
			return
		}

		// 切割步长
		// 1-3位数字
		for i := 1; i <= 3; i++ {
			if start+i > len(s) {
				break
			}
			sub := s[start : start+i]
			if isValid(sub) {
				path = append(path, sub)
				backtrack(start + i)
				path = path[:len(path)-1]
			}
		}
	}

	backtrack(0)
	return res
}

func isValid(s string) bool {
	if len(s) == 0 || (len(s) > 1 && s[0] == '0') {
		return false
	}
	num := 0
	for i := 0; i < len(s); i++ {
		num = num*10 + int(s[i]-'0')
	}
	return num >= 0 && num <= 255
}
func join(arr []string, sep string) string {
	if len(arr) == 0 {
		return ""
	}
	result := arr[0]
	for i := 1; i < len(arr); i++ {
		result += sep + arr[i]
	}
	return result
}
